package code.oldCode.dynamic;

import java.util.ArrayList;
import java.util.List;

public class DynamicMatrix {

    /**
     * 62. 不同路径
     *
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[][] path = new int[m][n];
        for (int i = 0; i < m; i++) {
            path[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            path[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                path[i][j] = path[i - 1][j] + path[i][j - 1];
            }
        }
        return path[m - 1][n - 1];
    }

    /**
     * 64. 最小路径和
     *
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        int len = grid.length, wid = grid[0].length;
        int[][] min = new int[len][wid];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < wid; j++) {
                if (i == 0 && j == 0) min[i][j] = grid[i][j];
                else if (i == 0) min[i][j] = grid[i][j] + min[i][j - 1];
                else if (j == 0) min[i][j] = grid[i][j] + min[i - 1][j];
                else min[i][j] = grid[i][j] + Math.min(min[i - 1][j], min[i][j - 1]);
            }
        }
        return min[len - 1][wid - 1];
    }

    /**
     * 63. 不同路径 II
     *
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int len = obstacleGrid.length, wid = obstacleGrid[0].length;
        int[][] path = new int[len][wid];
        // 开头就堵住直接答案为0
        if (obstacleGrid[0][0] == 1) return 0;
        else path[0][0] = 1;
        // 看第一列里是否有障碍，有的话下面都去不了
        for (int i = 1; i < len; i++) {
            if (obstacleGrid[i][0] == 0)
                path[i][0] = 1;
            else
                break;
        }
        // 看第一行里是否有障碍，有的话下面都去不了
        for (int i = 1; i < wid; i++) {
            if (obstacleGrid[0][i] == 0)
                path[0][i] = 1;
            else
                break;
        }
        for (int i = 1; i < len; i++) {
            for (int j = 1; j < wid; j++) {
                if (obstacleGrid[i][j] == 0)
                    path[i][j] = (obstacleGrid[i - 1][j] == 0 ? path[i - 1][j] : 0) + (obstacleGrid[i][j - 1] == 0 ? path[i][j - 1] : 0);
            }
        }
        return path[len - 1][wid - 1];
    }

    /**
     * 120. 三角形最小路径和
     *
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        List<List<Integer>> lists = new ArrayList<>();
        int len = triangle.size();
        for (int i = 1; i <= len; i++) {
            List<Integer> temp = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                temp.add(0);
            }
            lists.add(temp);
        }
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                if (i == 0 && j == 0)
                    lists.get(i).set(j, triangle.get(i).get(j));
                else if (j == 0)
                    lists.get(i).set(j, triangle.get(i).get(j) + lists.get(i - 1).get(j));
                else if (j == triangle.get(i).size() - 1)
                    lists.get(i).set(j, triangle.get(i).get(j) + lists.get(i - 1).get(lists.get(i - 1).size() - 1));
                else
                    lists.get(i).set(j, triangle.get(i).get(j) + Math.min(lists.get(i - 1).get(j - 1), lists.get(i - 1).get(j )));
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < lists.get(len - 1).size(); i++) {
            int number = lists.get(len - 1).get(i);
            min = Math.min(min, number);
        }
        return min;
    }

    /**
     * 931. 下降路径最小和
     * @param matrix
     * @return
     */
    public int minFallingPathSum(int[][] matrix) {
        int len = matrix.length;
        int[][] dp = new int[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (i == 0)
                    dp[i][j] = matrix[i][j];
                else if (j == 0)
                    dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j], dp[i - 1][j + 1]);
                else if (j == len - 1)
                    dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j - 1], dp[i - 1][j]);
                else
                    dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j + 1]));
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            min = Math.min(min, dp[len - 1][i]);
        }

        return min;
    }

    /**
     * 221. 最大正方形
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {
        // 1 1 1 1 0
        // 1 1 1 1 0
        // 1 1 1 1 1
        // 1 1 1 1 1
        // 0 0 1 1 1
        int len = matrix.length;
        int wid = matrix[0].length;
        int[][] dp = new int[len][wid];
        int max = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < wid; j++) {
                if (matrix[i][j] == '0')
                    continue;
                // 边线
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                }
                // 内部
                else {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
                }
                max = Math.max(dp[i][j], max);
            }
        }

        return max * max;
    }

    public static void main(String[] args) {
        DynamicMatrix dynamicMatrix = new DynamicMatrix();
        char[][] c = new char[5][5];
        c[0] = "11110".toCharArray();
        c[1] = "11110".toCharArray();
        c[2] = "11111".toCharArray();
        c[3] = "11111".toCharArray();
        c[4] = "00111".toCharArray();
        System.out.println(dynamicMatrix.maximalSquare(c));
    }
}
